package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName : _111_二叉树的最小深度_广度优先
 * @Author : 骆发茂
 * @Date: 2021/12/11 18:51
 * @Description :
 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * 起点是root根节点，终点是最靠近根节点的那个叶子节点
 * BFS相对DFS的最主要区别是：BFS找到的路径一定是最短的，但代价是空间复杂度比DFS大很多
 * 也就是说BFS常用的场景就是让你在一幅图是找到从起点start到终点end的最近距离
 * 当前这个题目，使用BFS，depth每增加一步，队列中的所有节点都向前进一一步，这个逻辑保证了一旦找到一个终点，走的步数是最少的
 * DFS实际上是靠递归的堆栈记录走过的路径的，你要找到最短路径，肯定要把二叉树中所有树杈都探索完，然后才能对比出最短路径有多长
 * BFS借助队列做到一步一步齐头并进，是可以在还没遍历完整棵树的时候就找到最短距离的。
 * DFS是线，BFS是面；DFS是单打独斗，而BFS是集体行动

 */
public class _111_二叉树的最小深度_广度优先_图灵andlc官方题解 {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.right == null && root.left == null) {
            return 1;
        }
        Queue<QueueNode> queue = new LinkedList<>();
        queue.offer(new QueueNode(root, 1));
        //直到队列是空的，就结束了
        //是BFS，保证了一层层的顺序加到队列中，然后判断一层中各个节点是否是叶子节点
        //是叶子节点就直接return了，即执行
        /*            if (node.left == null && node.right == null) {
                return depth;
            }*/
        while (!queue.isEmpty()) {
            /*queue.poll()
            检索并删除此队列的头部，
            如果此队列为空，则返回 {@code null}。
            */
            QueueNode nodeDepth = queue.poll();
            //取出队列里面的node节点
            TreeNode node = nodeDepth.node;
            //取出队列里面的node的深度
            int depth = nodeDepth.depth;
            //BFS借助队列做到一步一步齐头并进，是可以在还没遍历完整棵树的时候就找到最短距离的
            //使用BFS，depth每增加一步，队列中的所有节点都向前进一一步，这个逻辑保证了一旦找到一个终点，走的步数是最少的
            //已经找到距离根节点最近的叶子节点了
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right  != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }
        //永远不会出现的情况
        return 0;
    }

}